package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.ListNode;

public class MergeKLists {

    /**
     *
     * 利用归并算法简化为两个升序合并
     *
     * @param lists
     * k == lists.length
     * 0 <= k <= 10^4
     * 0 <= lists[i].length <= 500
     * -10^4 <= lists[i][j] <= 10^4
     * lists[i] 按 升序 排列
     * lists[i].length 的总和不超过 10^4
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        return mergeLists(lists, 0, lists.length - 1);
    }

    public ListNode mergeLists(ListNode[] lists, int begin, int end) {
        if (end - begin == 0) {
            return lists[begin];
        }
        if (end - begin == 1) {
            return merge2List(lists[begin], lists[end]);
        }
        int mid = (begin + end) / 2;
        ListNode node1 = mergeLists(lists, begin, mid);
        ListNode node2 = mergeLists(lists, mid + 1, end);
        return merge2List(node1, node2);
    }

    private ListNode merge2List(ListNode node1, ListNode node2) {
        ListNode root = new ListNode();
        ListNode tail = root;
        while (node1 != null || node2 != null) {
            if (node1 == null) {
                tail.next = node2;
                node2 = node2.next;
            } else if (node2 == null || node1.val < node2.val) {
                tail.next = node1;
                node1 = node1.next;
            } else {
                tail.next = node2;
                node2 = node2.next;
            }
            tail = tail.next;
        }
        return root.next;
    }
}
